package com.likou.second_challenge;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class q76 {

    public String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        Map<Character, Integer> sCountMap = new HashMap<>();
        Map<Character, Integer> tCountMap = new HashMap<>();
        int sCount = 0;
        int tCount = 0;

        for (int i = 0; i < tLen; i++) {
            tCountMap.put(t.charAt(i), tCountMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        tCount = tCountMap.size();

        int left = 0;
        int right = 0;
        String ans = "";
        int min = Integer.MAX_VALUE;
        while (right < sLen) {
            if (tCountMap.containsKey(s.charAt(right))) {
                sCountMap.put(s.charAt(right), sCountMap.getOrDefault(s.charAt(right), 0) + 1);

                if (Objects.equals(sCountMap.get(s.charAt(right)), tCountMap.get(s.charAt(right)))) {
                    sCount++;
                }
            }

            while (sCount == tCount) {
                if (right - left + 1 < min) {
                    ans = s.substring(left, right + 1);
                    min = right - left + 1;
                }

                if (tCountMap.containsKey(s.charAt(left))) {
                    Integer num = sCountMap.get(s.charAt(left));
                    num--;
                    sCountMap.put(s.charAt(left), num);

                    if (tCountMap.get(s.charAt(left)) > sCountMap.get(s.charAt(left))) {
                        sCount--;
                    }
                }
                left++;
            }
            right++;
        }

        return ans;
    }
}
